44. Единицы
В
арифметическом выражении разрешается использовать число 1, операции сложения,
умножения и скобки. Какое наименьшее количество единиц нужно использовать,
чтобы получить заданное натуральное число n?
Вход. Одно
число n (1 ≤ n ≤ 5000).
Выход. Искомое
количество единиц.
|
Пример входа |
Пример выхода |
|
7 |
6 |
РЕШЕНИЕ
динамическое
программирование
Анализ алгоритма
Пусть f(n) равно наименьшему количеству единиц,
при помощи которых можно составить число n.
Очевидно, что f(1) = 1.
Число 4 представимо либо в виде 4 = 1 + 1 + 1 + 1, либо
4 = (1 + 1) * (1 + 1). Однако в обоих случаях используется 4 единицы.
Следовательно f(4) = 4.
Рассмотрим
искомое выражение, результат которого равен n.
1. Пусть
последней выполненной в нем операцией было сложение. Пусть, например, первое
слагаемое i состоит из f(i) единиц, а второе слагаемое n – i
состоит из f(n – i) единиц. Значение i
следует выбрать таким, чтобы сумма f(i)
+ f(n – i) была минимальной.
При этом
значение i достаточно перебирать до n / 2, так как можно предположить, что
первое слагаемое не больше второго. Таким образом, имеет место соотношение:
f(n) = 
2. Пусть
последней выполненной в нем операцией было умножение. Пусть, например, первый
множитель i состоит из f(i) единиц, а второй множитель n / i
состоит из f(n / i) единиц. Этот случай имеет место, если n делится нацело на i.
Значение i следует выбрать таким, чтобы сумма f(i) + f(n / i) была минимальной.
Значение i достаточно перебирать от 2
до 
. Имеет место соотношение:
f(n) = 
Таким
образом
f(n) = 
Вычислим ответ для n = 7:
f(7) =
f(6) + f(1) = (f(2) + f(3)) + f(1) = 2 + 3 + 1 = 6
Число 7 можно представить 6 единицами, а именно:
7 = (1 + 1) * (1 + 1 + 1) + 1
Реализация алгоритма
Объявим
массив res[5001], инициализируем res[1] = 1.
int res[5001];
scanf("%d",&n);
res[1] = 1;
Далее
последовательно вычислим значения res[2], res[3], …, res[n] согласно выше приведенной формуле.
for(i = 2; i <= n; i++)
{
res[i] = i;
for(j = 1; 2 * j < i; j++)
if (res[j] + res[i-j] < res[i]) res[i] = res[j] +
res[i-j];
for(j = 2; j * j <= i; j++)
if (i % j == 0)
if (res[j] + res[i/j] < res[i]) res[i] = res[j] +
res[i/j];
}
Выводим
ответ.
printf("%d\n",res[n]);
Реализация алгоритма – рекурсия с запоминанием
#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 2000000000
using namespace
std;
int n;
int dp[5001];
int f(int
n)
{
if (n == 1) return 1;
if (dp[n] != -1) return
dp[n];
int res = INF;
for(int i = 1; i
<= n / 2; i++)
res = min(res,f(i)
+ f(n - i));
for(int i = 2; i * i
<= n; i++)
if (n % i == 0) res = min(res,f(i) + f(n/i));
return dp[n] = res;
}
int main(void)
{
memset(dp,-1,sizeof(dp));
scanf("%d",&n);
printf("%d\n",f(n));
return 0;
}
Java реализация
import java.util.*;
public class Main
{
public static int MAX = 5001;
static int res[] = new int[MAX];
public static void main(String[] args)
{
Scanner con = new
Scanner(System.in);
int n = con.nextInt();
res[1] = 1;
for(int i = 2; i <= n; i++)
{
res[i] = i;
for(int j = 1; 2 * j < i; j++)
if (res[j] + res[i-j] < res[i]) res[i] = res[j] + res[i-j];
for(int j = 2; j * j <= i; j++)
if (i % j == 0)
if (res[j] + res[i/j] < res[i]) res[i] = res[j] + res[i/j];
}
System.out.println(res[n]);
con.close();
}
}